class Solution:
    def totalNQueens(self, n: int) -> int:
        ans = 0
        col = [0] * n 
        
        def valid(r, c):
            for R in range(r):
                C = col[R]
                if r + c == R + C or r - c == R - C:
                    return False
            return True

        def dfs(r, s):
            if r == n:
                nonlocal ans
                ans += 1
                return
            for c in s:
                if valid(r, c):
                    col[r] = c
                    dfs(r + 1, s-{c})
        dfs(0, set(range(n)))
        return ans 